package com.linwen.excise.niuke._60;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author wlw
 * @date 2023/3/16 12:25 AM
 */
public class _43迷宫问题 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] maze = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }
        List<Node> path = new ArrayList<>();
        dfs(maze,0,0,path);
        for (Node node : path) {
            System.out.println(node);
        }
    }

    private static boolean dfs(int[][] maze, int x, int y, List<Node> path) {
        path.add(new Node(x,y));
        maze[x][y] = 1;
        // 出口
        if (x == maze.length - 1 && y == maze[0].length - 1) {
            return true;
        }
        if(x+1<maze.length&&maze[x+1][y]==0){// 下
            if(dfs(maze,x+1,y,path)){
                return true;
            }
        }
        if(x-1>=0&&maze[x-1][y]==0){//
            if(dfs(maze,x-1,y,path)){
                return true;
            }
        }
        if(y+1<maze[0].length&&maze[x][y+1]==0){// 下
            if(dfs(maze,x,y+1,path)){
                return true;
            }
        }
        if(y-1>=0&&maze[x][y-1]==0){// 下
            if(dfs(maze,x,y-1,path)){
                return true;
            }
        }
        path.remove(path.size()-1);
        return false;
    }

    static class Node{
        int x;
        int y;
        Node(int x,int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public String toString(){
            return "("+x+","+y+")";
        }
    }
}

